package leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by Ghost on 2014/11/20 0020.
 */
public class Combination_Sum_II {
    private LinkedList<Integer> list = new LinkedList<Integer>();
    private LinkedList<List<Integer>> rst = new LinkedList<List<Integer>>();

    private void combine(int[] num, int begin, int target, int sum) {
        if (begin >= num.length) {
            if (sum == target)
                rst.add(new LinkedList<Integer>(list));

        } else {
            for (int i = begin; i < num.length; i++) {
                if (sum + num[i] < target) {
                    list.add(num[i]);
                    combine(num, i + 1, target, sum + num[i]);
                    list.removeLast();
                } else if (sum + num[i] == target) {
                    list.add(num[i]);
                    if (!rst.contains(list))
                        rst.add((List<Integer>) list.clone());
                    list.removeLast();
                }
            }
        }
    }

    public List<List<Integer>> combinationSum2(int[] num, int target) {
        Arrays.sort(num);
        combine(num, 0, target, 0);
        return rst;
    }

    public static void main(String[] args) {
        Combination_Sum_II combination_sum_ii = new Combination_Sum_II();
        int[] num = {10,1,2,7,6,1,5};
        int target = 1;

        List<List<Integer>> list = combination_sum_ii.combinationSum2(num, target);
        for (List lis : list) {
            for (Object integer : lis) {
                System.out.print(" " + integer);
            }
            System.out.println();
        }
    }
}
